1. Field of the Invention
This invention relates to networks. In particular, the invention relates to network reliability.
2. Description of Related Art
In certain studies of reliability of computer networks, it is useful to be able to generate samples of a Bernoulli random vector whose components model the current state of some network element. For example, the individual Bernoulli variables may correspond to the links in the network, with a value of 1 indicating the link is functional or “up”, and a value of 0 indicating it is non-functional or “down”.
Existing work on network reliability usually assumes that the Bernoulli variables corresponding to the links are independent. This assumption means that the random samples can be obtained independently for the individual components. Under this assumption, if the probability of each link being up or down is specified, then the sampling problem is trivial. However, the independence assumption is not realistic for certain types of networks, such as those using free-space optical (FSO) links. In these networks, there are common factors that affect the states of the links. For example, weather conditions may affect links within a locality. If a particular FSO link is down due to heavy fog, then it is likely that nearby links are down as well. The states of the links in these types of networks are, therefore, correlated and/or dependent on each other. To characterize this correlation, a covariance matrix is used in addition to the means of the link variables. The necessity of providing a covariance matrix for a Bernoulli variables makes it difficult to generate random samples of the network state.
In addition, the computational requirements for the joint probability density of such random vector are enormous. This is because such a joint density is a discrete density having 2n components where n is the length of the random vector. For a vector of even moderate length, the number of components making up the discrete density is extremely large, over 1 billion for n=30.
Therefore, there is a need to have an efficient technique to generate a random vector for multivariate Bernoulli variables.